package chapter05_string;

/**
 * 描述：
 *      原问题：给定一个括号字符串，判断是不是整体有效的字符串
 *      进阶问题：给定一个括号字符串，返回最长的有效括号子串长度
 * @author hl
 * @date 2021/9/8 21:54
 */
public class BracketValid {
    public static void main(String[] args) {
        BracketValid main = new BracketValid();
        String str = "(())(a()())";
        boolean valid = main.isValid(str);
        System.out.println(valid);
        int count = main.maxLength(str);
        System.out.println(count);

    }
    /**
     * 原问题标准解答
     * @param str
     * @return
     */
    public boolean isValid(String str){
        if (str == null || str.equals("")) {
            return false;
        }
        int status = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) != '(' && str.charAt(i) != ')') {
                return false;
            }
            if (str.charAt(i) == ')' && --status < 0) {
                return false;
            }
            if (str.charAt(i) == '(') {
                status++;
            }
        }
        return status == 0;
    }


    public boolean isValid2(String str){
        if (str == null || str.length() == 0) {
            return false;
        }
        int lc = 0, rc = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(') {
                lc++;
            }else if (str.charAt(i) == ')') {
                rc++;
            }else{
                return false;
            }
            if (lc < rc || (i == str.length() - 1 && lc != rc)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 返回最长的有效括号长度，可以使用动态规划进行求解。
     *
     * dp[i]代表以i结尾的有效括号子串的最大长度，以dp[i-1]结尾的最长的有效括号长度范围在[i - dp[i-1], i - 1]这个范围，
     * 因此如果dp[i]如果能够在dp[i-1]的基础上进行扩张那么是最好的，如果不能扩张，那么以i结尾的最长有效字符为0。
     * 如何判断能否继续扩张呢？
     *      如果str[i]=='('，说明不能扩张，dp[i] = 0
     *      如果str[i]=='('，考查i-dp[i-1]-1是否为'('，如果是则说明可以在以i-1结尾的最长子串上进行扩张，并且需要加上dp[i-dp[i-1]-2]的值
     *                      如果i-dp[i-1]-1是否为')'，则dp[i]=0
     * @param str
     * @return
     */

    public int maxLength(String str){
        if (str == null || str.length() == 0) {
            return 0;
        }
        int[] dp = new int[str.length()];
        int res = 0;
        int preIndex = 0;
        for (int i = 1; i < str.length(); i++) {
            if(str.charAt(i) == ')'){
                preIndex = i - dp[i - 1] - 1;
                if (preIndex >= 0 && str.charAt(preIndex) == '(') {
                    dp[i] = dp[i - 1] + 2 + (preIndex > 0 ? dp[preIndex - 1] : 0);
                }
            }
            //res = Math.max(res, dp[i]);//虽然更加优雅，但是会多一次赋值的动作
            if (dp[i] > res) {
                res = dp[i];
            }
        }
        return res;
    }


    public int maxLength2(String str){
        if (str == null || str.length() == 0) {
            return 0;
        }
        int[] dp = new int[str.length()];
        int res = Integer.MIN_VALUE;
        int preIndex = 0;
        for (int i = 1; i < dp.length; i++) {
            if ((str.charAt(i) != '(' && str.charAt(i) != ')') || str.charAt(i) == '(') {
                dp[i] = 0;
            }else{
                preIndex = i - dp[i - 1] - 1;
                if (preIndex < 0 || (str.charAt(preIndex) != '(' && str.charAt(preIndex) != ')') || dp[preIndex] == ')') {
                    dp[i] = 0;
                }else{
                    dp[i] = dp[i - 1] + 2 + (preIndex > 0 ? dp[preIndex - 1] : 0);
                }
            }
            if (dp[i] > res) {
                res = dp[i];
            }
        }
        return res;
    }

}
